SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Line–line intersection</title>

</head>

Line–line intersection

</h1>

</header>

In <a href="Euclidean_geometry" title="Euclidean geometry">Euclidean geometry</a>, the intersection of a line and a line can be the <a href="Empty_set" title="Empty set">empty set</a>, a <a href="Point_(geometry)" title="Point (geometry)">point</a>, or another <a href="Line_(geometry)" title="Line (geometry)">line</a>. Distinguishing these cases and finding the <a href="Intersection_(Euclidean_geometry)" class="mw-redirect" title="Intersection (Euclidean geometry)">intersection</a> have uses, for example, in <a href="Computer_graphics" title="Computer graphics">computer graphics</a>, <a href="Motion_planning" title="Motion planning">motion planning</a>, and <a href="Collision_detection" title="Collision detection">collision detection</a>.

In <a href="Three-dimensional" class="mw-redirect" title="Three-dimensional">three-dimensional</a> Euclidean geometry, if two lines are not in the same <a href="Plane_(geometry)" class="mw-redirect" title="Plane (geometry)">plane</a>, they have no point of intersection <a href="#cite_note-1">[1]</a> and are called <a href="Skew_lines" title="Skew lines">skew lines</a>. If they are in the same plane, however, there are three possibilities: if they coincide (are not distinct lines), they have an <a href="Infinitude" class="mw-redirect" title="Infinitude">infinitude</a> of points in common (namely all of the points on either of them); if they are distinct but have the same <a href="Slope" title="Slope">slope</a>, they are said to be <a href="Parallel_(geometry)" title="Parallel (geometry)">parallel</a> and have no points in common; otherwise, they have a single point of intersection.

The distinguishing features of <a href="Non-Euclidean_geometry" title="Non-Euclidean geometry">non-Euclidean geometry</a> are the number and locations of possible intersections between two lines and the number of possible lines with no intersections (parallel lines) with a given line.

<div class="mw-heading mw-heading2"><h2 id="Formulas">Formulas</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">See also: <a href="Skew_lines#Formulas" title="Skew lines">Skew lines § Formulas</a></div>

A <a href="Necessary_condition" class="mw-redirect" title="Necessary condition">necessary condition</a> for two lines to intersect is that they are in the same plane—that is, are not skew lines. Satisfaction of this condition is equivalent to the <a href="Tetrahedron" title="Tetrahedron">tetrahedron</a> with vertices at two of the points on one line and two of the points on the other line being <a href="Degeneracy_(mathematics)" title="Degeneracy (mathematics)">degenerate</a> in the sense of having zero <a href="Volume" title="Volume">volume</a>. For the algebraic form of this condition, see <a href="Skew_lines#Testing_for_skewness" title="Skew lines">Skew lines § Testing for skewness</a>.

<div class="mw-heading mw-heading3"><h3 id="Given_two_points_on_each_line">Given two points on each line</h3></div>

First we consider the intersection of two lines L1 and L2 in two-dimensional space, with line L1 being defined by two distinct points (x1, y1) and (x2, y2), and line L2 being defined by two distinct points (x3, y3) and (x4, y4).<a href="#cite_note-Wolfram-2">[2]</a>

The intersection P of line L1 and L2 can be defined using <a href="Determinant" title="Determinant">determinants</a>.

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<mtr>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

</mtr>

<mtr>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

</mtr>

<mtr>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<mtr>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

</mtr>

<mtr>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

</mtr>

<mtr>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{x}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix}}&{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4}&y_{4}\end{vmatrix}}&{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}}\,\!\qquad P_{y}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4}&y_{4}\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}}\,\!}</annotation>

</semantics>

</math><img src="./e750e00a5179c59dd228cc3dcdb1818a4bb89c9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -15.671ex; margin-right: -0.387ex; width:60.371ex; height:32.509ex;" alt="{\displaystyle P_{x}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix}}&{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4}&y_{4}\end{vmatrix}}&{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}}\,\!\qquad P_{y}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4}&y_{4}\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}}\,\!}" loading="lazy"></dd></dl>

The determinants can be written out as:

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}P_{x}&={\frac {(x_{1}y_{2}-y_{1}x_{2})(x_{3}-x_{4})-(x_{1}-x_{2})(x_{3}y_{4}-y_{3}x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}\\[4px]P_{y}&={\frac {(x_{1}y_{2}-y_{1}x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}y_{4}-y_{3}x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}\end{aligned}}}</annotation>

</semantics>

</math><img src="./013a4193eae935296d58199bf902574a99c34a5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.338ex; width:56.635ex; height:13.843ex;" alt="{\displaystyle {\begin{aligned}P_{x}&={\frac {(x_{1}y_{2}-y_{1}x_{2})(x_{3}-x_{4})-(x_{1}-x_{2})(x_{3}y_{4}-y_{3}x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}\\[4px]P_{y}&={\frac {(x_{1}y_{2}-y_{1}x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}y_{4}-y_{3}x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}\end{aligned}}}" loading="lazy"></dd></dl>

When the two lines are parallel or coincident, the denominator is zero.

<div class="mw-heading mw-heading3"><h3 id="Given_two_points_on_each_line_segment">Given two points on each line segment</h3></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Intersection_(geometry)#Two_line_segments" title="Intersection (geometry)">Intersection_(geometry) § Two_line_segments</a></div>

The intersection point above is for the infinitely long lines defined by the points, rather than the <a href="Line_segment" title="Line segment">line segments</a> between the points, and can produce an intersection point not contained in either of the two line segments. In order to find the position of the intersection in respect to the line segments, we can define lines L1 and L2 in terms of first degree <a href="B%C3%A9zier_curve#Linear_curves" title="Bézier curve">Bézier</a> parameters:

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{1}={\begin{bmatrix}x_{1}\\y_{1}\end{bmatrix}}+t{\begin{bmatrix}x_{2}-x_{1}\\y_{2}-y_{1}\end{bmatrix}},\qquad L_{2}={\begin{bmatrix}x_{3}\\y_{3}\end{bmatrix}}+u{\begin{bmatrix}x_{4}-x_{3}\\y_{4}-y_{3}\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./b180feb8dad306a549cc755223444e3c9f010f95.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:57.81ex; height:6.176ex;" alt="{\displaystyle L_{1}={\begin{bmatrix}x_{1}\\y_{1}\end{bmatrix}}+t{\begin{bmatrix}x_{2}-x_{1}\\y_{2}-y_{1}\end{bmatrix}},\qquad L_{2}={\begin{bmatrix}x_{3}\\y_{3}\end{bmatrix}}+u{\begin{bmatrix}x_{4}-x_{3}\\y_{4}-y_{3}\end{bmatrix}}}" loading="lazy"></dd></dl>

(where t and u are real numbers). The intersection point of the lines is found with one of the following values of t or u, where

<mfrac>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t={\frac {\begin{vmatrix}x_{1}-x_{3}&x_{3}-x_{4}\\y_{1}-y_{3}&y_{3}-y_{4}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{4}\end{vmatrix}}}={\frac {(x_{1}-x_{3})(y_{3}-y_{4})-(y_{1}-y_{3})(x_{3}-x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}}</annotation>

</semantics>

</math><img src="./3037b45bc402892dc1273dc0c3b70532f3bcda39.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.838ex; width:68.042ex; height:12.843ex;" alt="{\displaystyle t={\frac {\begin{vmatrix}x_{1}-x_{3}&x_{3}-x_{4}\\y_{1}-y_{3}&y_{3}-y_{4}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{4}\end{vmatrix}}}={\frac {(x_{1}-x_{3})(y_{3}-y_{4})-(y_{1}-y_{3})(x_{3}-x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}}" loading="lazy"></dd></dl>

and

<mfrac>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u=-{\frac {\begin{vmatrix}x_{1}-x_{2}&x_{1}-x_{3}\\y_{1}-y_{2}&y_{1}-y_{3}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{4}\end{vmatrix}}}=-{\frac {(x_{1}-x_{2})(y_{1}-y_{3})-(y_{1}-y_{2})(x_{1}-x_{3})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}},}</annotation>

</semantics>

</math><img src="./d2febaeb9de5a981322cdba521b33934dbfe62ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.838ex; width:72.795ex; height:12.843ex;" alt="{\displaystyle u=-{\frac {\begin{vmatrix}x_{1}-x_{2}&x_{1}-x_{3}\\y_{1}-y_{2}&y_{1}-y_{3}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{4}\end{vmatrix}}}=-{\frac {(x_{1}-x_{2})(y_{1}-y_{3})-(y_{1}-y_{2})(x_{1}-x_{3})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}},}" loading="lazy"></dd></dl>

with

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (P_{x},P_{y})={\bigl (}x_{1}+t(x_{2}-x_{1}),\;y_{1}+t(y_{2}-y_{1}){\bigr )}\quad {\text{or}}\quad (P_{x},P_{y})={\bigl (}x_{3}+u(x_{4}-x_{3}),\;y_{3}+u(y_{4}-y_{3}){\bigr )}}</annotation>

</semantics>

</math><img src="./47fdf67cdcdd9e9cc4be4ed0bc638c959df90635.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:98.396ex; height:3.176ex;" alt="{\displaystyle (P_{x},P_{y})={\bigl (}x_{1}+t(x_{2}-x_{1}),\;y_{1}+t(y_{2}-y_{1}){\bigr )}\quad {\text{or}}\quad (P_{x},P_{y})={\bigl (}x_{3}+u(x_{4}-x_{3}),\;y_{3}+u(y_{4}-y_{3}){\bigr )}}" loading="lazy"></dd></dl>

There will be an intersection if 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1. The intersection point falls within the first line segment if 0 ≤ t ≤ 1, and it falls within the second line segment if 0 ≤ u ≤ 1. These inequalities can be tested without the need for division, allowing rapid determination of the existence of any line segment intersection before calculating its exact point.<a href="#cite_note-GGIII-3">[3]</a>

In the case where the two line segments share an x axis and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{2}=x_{1}+1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{2}=x_{1}+1}</annotation>

</semantics>

</math><img src="./fb0180f001a6838cd26956584ebc47815829c09d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.869ex; height:2.509ex;" alt="{\displaystyle x_{2}=x_{1}+1}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> simplify to

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=u={\frac {y_{1}-y_{3}}{y_{1}-y_{2}-y_{3}+y_{4}}},}</annotation>

</semantics>

</math>

with

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (P_{x},P_{y})={\bigl (}x_{1}+t,\;y_{1}+t(y_{2}-y_{1}){\bigr )}\quad {\text{or}}\quad (P_{x},P_{y})={\bigl (}x_{1}+t,\;y_{3}+t(y_{4}-y_{3}){\bigr )}.}</annotation>

</semantics>

</math>

<div class="mw-heading mw-heading3"><h3 id="Given_two_line_equations">Given two line equations</h3></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Intersection_(geometry)#Two_lines" title="Intersection (geometry)">Intersection_(geometry) § Two_lines</a></div>

The x and y coordinates of the point of intersection of two non-vertical lines can easily be found using the following substitutions and rearrangements.

Suppose that two lines have the equations y = ax + c and y = bx + d where a and b are the <a href="Slope" title="Slope">slopes</a> (gradients) of the lines and where c and d are the y-intercepts of the lines. At the point where the two lines intersect (if they do), both y coordinates will be the same, hence the following equality:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ax+c=bx+d.}</annotation>

</semantics>

</math><img src="./d6d09b52dff9b1354e1d0d1e383680799f9530e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:16.536ex; height:2.343ex;" alt="{\displaystyle ax+c=bx+d.}" loading="lazy"></dd></dl>

We can rearrange this expression in order to extract the value of x,

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ax-bx=d-c,}</annotation>

</semantics>

</math><img src="./8220888be24a3f2bb735c2e7613fe0d651ea29b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.536ex; height:2.509ex;" alt="{\displaystyle ax-bx=d-c,}" loading="lazy"></dd></dl>

and so,

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x={\frac {d-c}{a-b}}.}</annotation>

</semantics>

</math><img src="./b648fabd05ebf1703f11a55fcc29f3a438b84534.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:10.979ex; height:5.676ex;" alt="{\displaystyle x={\frac {d-c}{a-b}}.}" loading="lazy"></dd></dl>

To find the y coordinate, all we need to do is substitute the value of x into either one of the two line equations, for example, into the first:

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=a{\frac {d-c}{a-b}}+c.}</annotation>

</semantics>

</math><img src="./c4807b1aada38c4daf9f4d187f9594c82ed72365.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:15.882ex; height:5.676ex;" alt="{\displaystyle y=a{\frac {d-c}{a-b}}+c.}" loading="lazy"></dd></dl>

Hence, the point of intersection is

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=\left({\frac {d-c}{a-b}},a{\frac {d-c}{a-b}}+c\right).}</annotation>

</semantics>

</math><img src="./dd0c8920e7d05a752bb8084ddf066f3ac1196f26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:27.218ex; height:6.176ex;" alt="{\displaystyle P=\left({\frac {d-c}{a-b}},a{\frac {d-c}{a-b}}+c\right).}" loading="lazy"></dd></dl>

Note that if a = b then the two lines are <a href="Parallel_(geometry)" title="Parallel (geometry)">parallel</a> and they do not intersect, unless c = d as well, in which case the lines are coincident and they intersect at every point.

<div class="mw-heading mw-heading3"><h3 id="Using_homogeneous_coordinates">Using homogeneous coordinates</h3></div>

By using <a href="Homogeneous_coordinates" title="Homogeneous coordinates">homogeneous coordinates</a>, the intersection point of two implicitly defined lines can be determined quite easily. In 2D, every point can be defined as a projection of a 3D point, given as the ordered triple (x, y, w). The mapping from 3D to 2D coordinates is (x′, y′) = (<style data-mw-deduplicate="TemplateStyles:r1214402035">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}

/* end https://en.wikipedia.org/ */

</style>⁠x/w⁠, ⁠y/w⁠). We can convert 2D points to homogeneous coordinates by defining them as (x, y, 1).

Assume that we want to find intersection of two infinite lines in 2-dimensional space, defined as a1x + b1y + c1 = 0 and a2x + b2y + c2 = 0. We can represent these two lines in <a href="Line_coordinates" title="Line coordinates">line coordinates</a> as U1 = (a1, b1, c1) and U2 = (a2, b2, c2). The intersection P′ of two lines is then simply given by<a href="#cite_note-4">[4]</a>

<msup>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P'=(a_{p},b_{p},c_{p})=U_{1}\times U_{2}=(b_{1}c_{2}-b_{2}c_{1},a_{2}c_{1}-a_{1}c_{2},a_{1}b_{2}-a_{2}b_{1})}</annotation>

</semantics>

</math><img src="./64a98c8d2431dd018fafc1b9083f8fa6fe856639.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:68.2ex; height:3.176ex;" alt="{\displaystyle P'=(a_{p},b_{p},c_{p})=U_{1}\times U_{2}=(b_{1}c_{2}-b_{2}c_{1},a_{2}c_{1}-a_{1}c_{2},a_{1}b_{2}-a_{2}b_{1})}" loading="lazy"></dd></dl>

If cp = 0, the lines do not intersect.

<div class="mw-heading mw-heading2"><h2 id="More_than_two_lines">More than two lines</h2></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Skew_lines#More_than_two_lines" title="Skew lines">Skew lines § More than two lines</a></div>

The intersection of two lines can be generalized to involve additional lines. The existence of and expression for the n-line intersection problem are as follows.

<div class="mw-heading mw-heading3"><h3 id="In_two_dimensions">In two dimensions</h3></div>

In two dimensions, more than two lines <a href="Almost_certainly" class="mw-redirect" title="Almost certainly">almost certainly</a> do not intersect at a single point. To determine if they do and, if so, to find the intersection point, write the ith equation (i = 1, …, n) as

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}=b_{i},}</annotation>

</semantics>

</math><img src="./298a26cf6811e0247994cd227688e2a3f8b1dc6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:20.149ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}=b_{i},}" loading="lazy"></dd></dl>

and stack these equations into matrix form as

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {A} \mathbf {w} =\mathbf {b} ,}</annotation>

</semantics>

</math><img src="./518868e98c6a7166eb0312feb0c1485d9e09664f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.181ex; height:2.509ex;" alt="{\displaystyle \mathbf {A} \mathbf {w} =\mathbf {b} ,}" loading="lazy"></dd></dl>

where the ith row of the n × 2 matrix A is [ai1, ai2], w is the 2 × 1 vector <big><big>[</big></big>x y<big><big>]</big></big>, and the ith element of the column vector b is bi. If A has independent columns, its <a href="Matrix_rank" class="mw-redirect" title="Matrix rank">rank</a> is 2. Then if and only if the rank of the <a href="Augmented_matrix" title="Augmented matrix">augmented matrix</a> [A | b] is also 2, there exists a solution of the matrix equation and thus an intersection point of the n lines. The intersection point, if it exists, is given by

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msup>

<mrow>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {w} =\mathbf {A} ^{\mathrm {g} }\mathbf {b} =\left(\mathbf {A} ^{\mathsf {T}}\mathbf {A} \right)^{-1}\mathbf {A} ^{\mathsf {T}}\mathbf {b} ,}</annotation>

</semantics>

</math><img src="./db7a77f3c0c561597672d6bbab223389fbeb265e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:28.043ex; height:3.843ex;" alt="{\displaystyle \mathbf {w} =\mathbf {A} ^{\mathrm {g} }\mathbf {b} =\left(\mathbf {A} ^{\mathsf {T}}\mathbf {A} \right)^{-1}\mathbf {A} ^{\mathsf {T}}\mathbf {b} ,}" loading="lazy"></dd></dl>

where Ag is the <a href="Moore%E2%80%93Penrose_inverse" title="Moore–Penrose inverse">Moore–Penrose generalized inverse</a> of A (which has the form shown because A has full column rank). Alternatively, the solution can be found by jointly solving any two independent equations. But if the rank of A is only 1, then if the rank of the augmented matrix is 2 there is no solution but if its rank is 1 then all of the lines coincide with each other.

<div class="mw-heading mw-heading3"><h3 id="In_three_dimensions">In three dimensions</h3></div>

The above approach can be readily extended to three dimensions. In three or more dimensions, even two lines almost certainly do not intersect; pairs of non-parallel lines that do not intersect are called <a href="Skew_lines" title="Skew lines">skew lines</a>. But if an intersection does exist it can be found, as follows.

In three dimensions a line is represented by the intersection of two planes, each of which has an equation of the form

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}&a_{i3}\end{bmatrix}}{\begin{bmatrix}x\\y\\z\end{bmatrix}}=b_{i}.}</annotation>

</semantics>

</math><img src="./602b520329d25a88d529d641c55abfe7878b7ebd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.171ex; width:25.969ex; height:9.509ex;" alt="{\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}&a_{i3}\end{bmatrix}}{\begin{bmatrix}x\\y\\z\end{bmatrix}}=b_{i}.}" loading="lazy"></dd></dl>

Thus a set of n lines can be represented by 2n equations in the 3-dimensional coordinate vector w:

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {A} \mathbf {w} =\mathbf {b} }</annotation>

</semantics>

</math><img src="./916c1f6081563dfc96d29f08660ab0b00d6f9fbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.534ex; height:2.176ex;" alt="{\displaystyle \mathbf {A} \mathbf {w} =\mathbf {b} }" loading="lazy"></dd></dl>

where now A is 2n × 3 and b is 2n × 1. As before there is a unique intersection point if and only if A has full column rank and the augmented matrix [A | b] does not, and the unique intersection if it exists is given by

</mrow>

<msup>

<mrow>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {w} =\left(\mathbf {A} ^{\mathsf {T}}\mathbf {A} \right)^{-1}\mathbf {A} ^{\mathsf {T}}\mathbf {b} .}</annotation>

</semantics>

</math><img src="./b30ef9641ae1df1fb02047cedd808b9286f66607.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:20.386ex; height:3.843ex;" alt="{\displaystyle \mathbf {w} =\left(\mathbf {A} ^{\mathsf {T}}\mathbf {A} \right)^{-1}\mathbf {A} ^{\mathsf {T}}\mathbf {b} .}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Nearest_points_to_skew_lines">Nearest points to skew lines</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Skew_lines#Nearest_points" title="Skew lines">Skew lines § Nearest points</a></div>

In two or more dimensions, we can usually find a point that is mutually closest to two or more lines in a <a href="Least-squares" class="mw-redirect" title="Least-squares">least-squares</a> sense.

<div class="mw-heading mw-heading3"><h3 id="In_two_dimensions_2">In two dimensions</h3></div>

In the two-dimensional case, first, represent line i as a point pi on the line and a <a href="Unit_vector" title="Unit vector">unit</a> <a href="Normal_vector" class="mw-redirect" title="Normal vector">normal vector</a> n̂i, perpendicular to that line. That is, if x1 and x2 are points on line 1, then let p1 = x1 and let

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {\hat {n}} _{1}:={\begin{bmatrix}0&-1\\1&0\end{bmatrix}}{\frac {\mathbf {x} _{2}-\mathbf {x} _{1}}{\|\mathbf {x} _{2}-\mathbf {x} _{1}\|}}}</annotation>

</semantics>

</math><img src="./274aa7f73379f17bce3903650683e8a7827fabd6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:26.879ex; height:6.343ex;" alt="{\displaystyle \mathbf {\hat {n}} _{1}:={\begin{bmatrix}0&-1\\1&0\end{bmatrix}}{\frac {\mathbf {x} _{2}-\mathbf {x} _{1}}{\|\mathbf {x} _{2}-\mathbf {x} _{1}\|}}}" loading="lazy"></dd></dl>

which is the unit vector along the line, rotated by a right angle.

The distance from a point x to the line (p, n̂) is given by

</mrow>

</mrow>

</mrow>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

<mover>

</mover>

</mrow>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

<mover>

</mover>

</mrow>

</mrow>

<mrow>

<mrow>

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

<msqrt>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

<mover>

</mover>

</mrow>

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d{\bigl (}\mathbf {x} ,(\mathbf {p} ,\mathbf {\hat {n}} ){\bigr )}={\bigl |}(\mathbf {x} -\mathbf {p} )\cdot \mathbf {\hat {n}} {\bigr |}=\left|(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\mathbf {\hat {n}} \right|=\left|\mathbf {\hat {n}} ^{\mathsf {T}}(\mathbf {x} -\mathbf {p} )\right|={\sqrt {(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\mathbf {\hat {n}} \mathbf {\hat {n}} ^{\mathsf {T}}(\mathbf {x} -\mathbf {p} )}}.}</annotation>

</semantics>

</math><img src="./14e42c1e230c36db7733149bbeb0a22d60299f3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.671ex; width:83.091ex; height:4.843ex;" alt="{\displaystyle d{\bigl (}\mathbf {x} ,(\mathbf {p} ,\mathbf {\hat {n}} ){\bigr )}={\bigl |}(\mathbf {x} -\mathbf {p} )\cdot \mathbf {\hat {n}} {\bigr |}=\left|(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\mathbf {\hat {n}} \right|=\left|\mathbf {\hat {n}} ^{\mathsf {T}}(\mathbf {x} -\mathbf {p} )\right|={\sqrt {(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\mathbf {\hat {n}} \mathbf {\hat {n}} ^{\mathsf {T}}(\mathbf {x} -\mathbf {p} )}}.}" loading="lazy"></dd></dl>

And so the squared distance from a point x to a line is

</mrow>

</mrow>

</mrow>

<mover>

</mover>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

<mrow>

<mrow>

<mover>

</mover>

</mrow>

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d{\bigl (}\mathbf {x} ,(\mathbf {p} ,\mathbf {\hat {n}} ){\bigr )}^{2}=(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\left(\mathbf {\hat {n}} \mathbf {\hat {n}} ^{\mathsf {T}}\right)(\mathbf {x} -\mathbf {p} ).}</annotation>

</semantics>

</math><img src="./32f15e8a0f8a966f2a093b887ec301c18903e076.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:40.719ex; height:4.843ex;" alt="{\displaystyle d{\bigl (}\mathbf {x} ,(\mathbf {p} ,\mathbf {\hat {n}} ){\bigr )}^{2}=(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\left(\mathbf {\hat {n}} \mathbf {\hat {n}} ^{\mathsf {T}}\right)(\mathbf {x} -\mathbf {p} ).}" loading="lazy"></dd></dl>

The sum of squared distances to many lines is the <a href="Loss_function" title="Loss function">cost function</a>:

</mrow>

</mrow>

</munder>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<mrow>

<mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(\mathbf {x} )=\sum _{i}(\mathbf {x} -\mathbf {p} _{i})^{\mathsf {T}}\left(\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)(\mathbf {x} -\mathbf {p} _{i}).}</annotation>

</semantics>

</math><img src="./0ee99345dd74a1b056833780e0e3e3b5649d4fa6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:38.81ex; height:6.009ex;" alt="{\displaystyle E(\mathbf {x} )=\sum _{i}(\mathbf {x} -\mathbf {p} _{i})^{\mathsf {T}}\left(\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)(\mathbf {x} -\mathbf {p} _{i}).}" loading="lazy"></dd></dl>

This can be rearranged:

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</munder>

<msup>

</mrow>

</mrow>

</msup>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

<mrow>

<mrow>

</mrow>

</munder>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

<mrow>

<mrow>

</mrow>

</munder>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</munder>

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}E(\mathbf {x} )&=\sum _{i}\mathbf {x} ^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {x} -\mathbf {x} ^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}-\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {x} +\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\\&=\mathbf {x} ^{\mathsf {T}}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} -2\mathbf {x} ^{\mathsf {T}}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right)+\sum _{i}\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}.\end{aligned}}}</annotation>

</semantics>

</math><img src="./efbc8441860702bab338097c323c73ee9057cb39.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.745ex; margin-bottom: -0.259ex; width:65.794ex; height:13.176ex;" alt="{\displaystyle {\begin{aligned}E(\mathbf {x} )&=\sum _{i}\mathbf {x} ^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {x} -\mathbf {x} ^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}-\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {x} +\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\\&=\mathbf {x} ^{\mathsf {T}}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} -2\mathbf {x} ^{\mathsf {T}}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right)+\sum _{i}\mathbf {p} _{i}^{\mathsf {T}}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}.\end{aligned}}}" loading="lazy"></dd></dl>

To find the minimum, we differentiate with respect to x and set the result equal to the zero vector:

<mfrac>

<mrow>

</mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

<mrow>

</mrow>

</munder>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

<mrow>

<mrow>

</mrow>

</munder>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {\partial E(\mathbf {x} )}{\partial \mathbf {x} }}={\boldsymbol {0}}=2\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} -2\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right)}</annotation>

</semantics>

</math><img src="./424f0b34f839b19fc40878fe7aba1bafd45e749e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:49.797ex; height:7.509ex;" alt="{\displaystyle {\frac {\partial E(\mathbf {x} )}{\partial \mathbf {x} }}={\boldsymbol {0}}=2\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} -2\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right)}" loading="lazy"></dd></dl>

so

<mrow>

<mrow>

</mrow>

</munder>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</mrow>

</munder>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} =\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}}</annotation>

</semantics>

</math><img src="./525909b22e699148d2a4ad6c9ff895056f267c97.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:28.591ex; height:7.509ex;" alt="{\displaystyle \left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} =\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}}" loading="lazy"></dd></dl>

and so

</mrow>

<msup>

<mrow>

<mrow>

</mrow>

</munder>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msup>

<mrow>

<mrow>

</mrow>

</munder>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} =\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)^{-1}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right).}</annotation>

</semantics>

</math><img src="./59933487d2480701381930215278b1abb55dd234.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:35.639ex; height:8.009ex;" alt="{\displaystyle \mathbf {x} =\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)^{-1}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right).}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="In_more_than_two_dimensions">In more than two dimensions</h3></div>

While n̂i is not well-defined in more than two dimensions, this can be generalized to any number of dimensions by noting that n̂i n̂iT is simply the symmetric matrix with all eigenvalues unity except for a zero eigenvalue in the direction along the line providing a <a href="Seminorm" title="Seminorm">seminorm</a> on the distance between pi and another point giving the distance to the line. In any number of dimensions, if v̂i is a unit vector along the ith line, then

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}}</annotation>

</semantics>

</math><img src="./b7559e75c74d9c8df3e20ec175e23ebcbe4e7908.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.122ex; height:3.343ex;" alt="{\displaystyle \mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}}" loading="lazy"> becomes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}}">

</mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}}</annotation>

</semantics>

</math><img src="./98d0b18b738c16ff6b319b0b2f35cafa8ca825cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.827ex; height:3.343ex;" alt="{\displaystyle \mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}}" loading="lazy"></dd></dl>

where I is the <a href="Identity_matrix" title="Identity matrix">identity matrix</a>, and so<a href="#cite_note-5">[5]</a>

<msup>

<mrow>

<mrow>

</mrow>

</munder>

</mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msup>

<mrow>

<mrow>

</mrow>

</munder>

<mrow>

<mrow>

</mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=\left(\sum _{i}\mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}\right)^{-1}\left(\sum _{i}\left(\mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}\right)\mathbf {p} _{i}\right).}</annotation>

</semantics>

</math><img src="./59b6dd18514dfd3297afdc77848b78bdc719c659.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:46.131ex; height:8.009ex;" alt="{\displaystyle x=\left(\sum _{i}\mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}\right)^{-1}\left(\sum _{i}\left(\mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}\right)\mathbf {p} _{i}\right).}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="General_derivation">General derivation</h3></div>

In order to find the intersection point of a set of lines, we calculate the point with minimum distance to them. Each line is defined by an origin ai and a unit direction vector n̂i. The square of the distance from a point p to one of the lines is given from Pythagoras:

</mrow>

</mrow>

</msubsup>

<msup>

<mrow>

<mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

<msup>

<mrow>

<mrow>

<msup>

<mrow>

<mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

<msup>

<mrow>

<mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

<mrow>

<mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

<msup>

<mrow>

<mrow>

<msup>

<mrow>

<mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{i}^{2}=\left\|\mathbf {p} -\mathbf {a} _{i}\right\|^{2}-\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}=\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\left(\mathbf {p} -\mathbf {a} _{i}\right)-\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}}</annotation>

</semantics>

</math><img src="./7abdcab4695060f64e75e6881643c4fdc6ff0af9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:73.562ex; height:5.176ex;" alt="{\displaystyle d_{i}^{2}=\left\|\mathbf {p} -\mathbf {a} _{i}\right\|^{2}-\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}=\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\left(\mathbf {p} -\mathbf {a} _{i}\right)-\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}}" loading="lazy"></dd></dl>

where (p − ai)T n̂i is the projection of p − ai on line i. The sum of distances to the square to all lines is

</mrow>

</munder>

</mrow>

</mrow>

</msubsup>

</mrow>

</munder>

<mrow>

<mrow>

<msup>

<mrow>

<mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

</mrow>

<mrow>

<mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

<msup>

<mrow>

<mrow>

<msup>

<mrow>

<mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i}d_{i}^{2}=\sum _{i}\left({\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}}\left(\mathbf {p} -\mathbf {a} _{i}\right)-{\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}}\right)}</annotation>

</semantics>

</math><img src="./f02661a600d95c6a793fac3a0ad65554b0436f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:53.024ex; height:6.676ex;" alt="{\displaystyle \sum _{i}d_{i}^{2}=\sum _{i}\left({\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}}\left(\mathbf {p} -\mathbf {a} _{i}\right)-{\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}}\right)}" loading="lazy"></dd></dl>

To minimize this expression, we differentiate it with respect to p.

</mrow>

</munder>

<mrow>

<mrow>

<mrow>

<mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

<mrow>

<mrow>

<msup>

<mrow>

<mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i}\left(2\left(\mathbf {p} -\mathbf {a} _{i}\right)-2\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)\mathbf {\hat {n}} _{i}\right)={\boldsymbol {0}}}</annotation>

</semantics>

</math><img src="./80a0b924e667c22a1b64d075aae8fdda547ec1f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:42.445ex; height:6.009ex;" alt="{\displaystyle \sum _{i}\left(2\left(\mathbf {p} -\mathbf {a} _{i}\right)-2\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)\mathbf {\hat {n}} _{i}\right)={\boldsymbol {0}}}" loading="lazy"></dd></dl>

</mrow>

</munder>

<mrow>

<mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</munder>

<mrow>

<mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

<mrow>

<mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i}\left(\mathbf {p} -\mathbf {a} _{i}\right)=\sum _{i}\left(\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\left(\mathbf {p} -\mathbf {a} _{i}\right)}</annotation>

</semantics>

</math><img src="./32c1a8d36fe851f3d33a670233c53f62f94e21d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:35.335ex; height:6.009ex;" alt="{\displaystyle \sum _{i}\left(\mathbf {p} -\mathbf {a} _{i}\right)=\sum _{i}\left(\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\left(\mathbf {p} -\mathbf {a} _{i}\right)}" loading="lazy"></dd></dl>

which results in

<mrow>

<mrow>

</mrow>

</munder>

<mrow>

<mrow>

</mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</munder>

<mrow>

<mrow>

</mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(\sum _{i}\left(\mathbf {I} -\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\right)\mathbf {p} =\sum _{i}\left(\mathbf {I} -\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {a} _{i}}</annotation>

</semantics>

</math><img src="./196fe20984524b15ca8f392ae9c43368289a7b71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:42.126ex; height:7.509ex;" alt="{\displaystyle \left(\sum _{i}\left(\mathbf {I} -\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\right)\mathbf {p} =\sum _{i}\left(\mathbf {I} -\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {a} _{i}}" loading="lazy"></dd></dl>

where I is the <a href="Identity_matrix" title="Identity matrix">identity matrix</a>. This is a matrix Sp = C, with solution p = S+C, where S+ is the <a href="Pseudo-inverse" class="mw-redirect" title="Pseudo-inverse">pseudo-inverse</a> of S.

<div class="mw-heading mw-heading2"><h2 id="Non-Euclidean_geometry">Non-Euclidean geometry</h2></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Parallel_postulate" title="Parallel postulate">Parallel postulate</a></div><style data-mw-deduplicate="TemplateStyles:r1251242444">

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

In <a href="Spherical_geometry" title="Spherical geometry">spherical geometry</a>, any two great circles intersect.<a href="#cite_note-:0-6">[6]</a>

In <a href="Hyperbolic_geometry" title="Hyperbolic geometry">hyperbolic geometry</a>, given any line and any point, there are infinitely many lines through that point that do not intersect the given line.<a href="#cite_note-:0-6">[6]</a>

<ul><li><a href="Line_segment_intersection" class="mw-redirect" title="Line segment intersection">Line segment intersection</a></li>

<li><a href="Projective_plane#Lines_joining_points_and_intersection_of_lines_.28using_duality.29" title="Projective plane">Line intersection in projective space</a></li>

<li><a href="Distance_between_two_parallel_lines" title="Distance between two parallel lines">Distance between two parallel lines</a></li>

<li><a href="Distance_from_a_point_to_a_line" title="Distance from a point to a line">Distance from a point to a line</a></li>

<li><a href="Line%E2%80%93plane_intersection" title="Line–plane intersection">Line–plane intersection</a></li>

<li><a href="Parallel_postulate" title="Parallel postulate">Parallel postulate</a></li>

<li><a href="Triangulation_(computer_vision)" title="Triangulation (computer vision)">Triangulation (computer vision)</a></li>

<li><a href="Intersection_(Euclidean_geometry)" class="mw-redirect" title="Intersection (Euclidean geometry)">Intersection (Euclidean geometry) § Two line segments</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCook2023" class="citation web cs1">Cook, Jeremy (November 21, 2023). <a rel="nofollow" class="external text" href="https://study.com/academy/lesson/coplanar-lines-in-geometry-definition-lesson-quiz.html#:~:text=Non%2Dcoplanar%20lines%20are%20lines%20that%20are%20not%20on%20the,not%20in%20the%20same%20plane.">"Coplanar Lines in Geometry | Definition, Diagrams & Examples"</a>. Retrieved November 1, 2024.</cite>

</li>

<li id="cite_note-Wolfram-2"><a href="#cite_ref-Wolfram_2-0">^</a> <cite id="CITEREFWeisstein" class="citation web cs1"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/Line-LineIntersection.html">"Line-Line Intersection"</a>. <a href="MathWorld" title="MathWorld">MathWorld</a>. Retrieved 2008-01-10.</cite>

</li>

<li id="cite_note-GGIII-3"><a href="#cite_ref-GGIII_3-0">^</a> <cite id="CITEREFAntonio1992" class="citation book cs1">Antonio, Franklin (1992). "Chapter IV.6: Faster Line Segment Intersection". In Kirk, David (ed.). Graphics Gems III. Academic Press, Inc. pp. 199–202. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-12-059756-X</bdi>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFBirchfield1998" class="citation web cs1">Birchfield, Stanley (1998-04-23). <a rel="nofollow" class="external text" href="http://robotics.stanford.edu/~birch/projective/node4.html">"Homogeneous coordinates"</a>. robotics.stanford.edu. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20000929025956/http://robotics.stanford.edu/~birch/projective/node4.html">Archived</a> from the original on 2000-09-29. Retrieved 2015-08-18.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFTraa2013" class="citation web cs1">Traa, Johannes (2013). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170912055605/http://cal.cs.illinois.edu/~johannes/research/LS_line_intersect.pdf">"Least-Squares Intersection of Lines"</a> (PDF). cal.cs.illinois.edu. Archived from <a rel="nofollow" class="external text" href="http://cal.cs.illinois.edu/~johannes/research/LS_line_intersect.pdf">the original</a> (PDF) on 2017-09-12. Retrieved 2018-08-30.</cite>

</li>

<li id="cite_note-:0-6">^ <a href="#cite_ref-:0_6-0">a</a> <a href="#cite_ref-:0_6-1">b</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://math.berkeley.edu/~kpmann/Hyperbolic%20and%20Spherical%20geometries.pdf">"Exploring Hyperbolic Space"</a> (PDF). math.berkeley.edu. Retrieved 2022-06-03.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm">Distance between Lines and Segments with their Closest Point of Approach</a>, applicable to two, three, or more dimensions.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-01" href="https://en.wikipedia.org/wiki/?title=Line%E2%80%93line_intersection&oldid=1288274748">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>